{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Subarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #divide-and-conquer #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #分治 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSubArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大子数组和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。</p>\n",
    "\n",
    "<p><strong>子数组 </strong>是数组中的一个连续部分。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [-2,1,-3,4,-1,2,1,-5,4]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>连续子数组&nbsp;[4,-1,2,1] 的和最大，为&nbsp;6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5,4,-1,7,8]\n",
    "<strong>输出：</strong>23\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>如果你已经实现复杂度为 <code>O(n)</code> 的解法，尝试使用更为精妙的 <strong>分治法</strong> 求解。</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-subarray](https://leetcode.cn/problems/maximum-subarray/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-subarray](https://leetcode.cn/problems/maximum-subarray/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-2,1,-3,4,-1,2,1,-5,4]', '[1]', '[5,4,-1,7,8]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s, res = 0, nums[0]\n",
    "        for num in nums:\n",
    "            s += num\n",
    "            res = max(res, s)\n",
    "            if s < 0:\n",
    "                s = 0\n",
    "        return res\n",
    "    \n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        dif = [y - x for x, y in zip(nums1, nums2)]\n",
    "        return max(sum(nums1) + self.maxSubArray(dif), sum(nums2) + self.maxSubArray(list(map(lambda x: -x, dif))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        d = [nums1[i] - nums2[i] for i in range(len(nums1))]\n",
    "        d2 = [nums2[i] - nums1[i] for i in range(len(nums1))]\n",
    "\n",
    "        return max(sum(nums1) + self.maxSubArray(d2),sum(nums2) + self.maxSubArray(d))\n",
    "\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        ans = -inf\n",
    "        min_pre_sum = pre_sum = 0\n",
    "        for x in nums:\n",
    "            pre_sum += x\n",
    "            ans = max(ans, pre_sum - min_pre_sum)\n",
    "            min_pre_sum = min(min_pre_sum, pre_sum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        dct = {}\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        dct[0] = -1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            pre += nums[i]\n",
    "            if pre - k in dct and i - dct[pre - k] > ans:\n",
    "                ans = i - dct[pre - k]\n",
    "            if pre not in dct:\n",
    "                dct[pre] = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        pre_sum = 0\n",
    "        d = {0:-1}\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            pre_sum += nums[i]\n",
    "            if pre_sum == k:\n",
    "                ans = i + 1\n",
    "            elif pre_sum - k in d:\n",
    "                ans = max(ans, i - d[pre_sum-k])\n",
    "            if pre_sum not in d:\n",
    "                d[pre_sum] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Prefix sum. Time O(n) Space O(n)\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        curSum = 0\n",
    "        # sum of a[0]...a[i], i.e. the first i elems: i\n",
    "        prefix = {0: 0}\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            curSum += nums[i]\n",
    "            if curSum - k in prefix.keys():\n",
    "                # prefix[curSum - k]: j, means sum of the first j elems, i.e. a[0]...a[j-1], is prefix[curSum - k]\n",
    "                # sum of a[j]...a[i] is k. Length of the array is i - j + 1\n",
    "                res = max(res, i - prefix[curSum - k] + 1)\n",
    "            if curSum not in prefix.keys():\n",
    "                # curSum is the sum of the first i + 1 elems\n",
    "                prefix[curSum] = i + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        # 前缀和，记录每个前缀和首次出现的位置\n",
    "        summ_dict={0:-1}\n",
    "        summ=0\n",
    "        ans=0\n",
    "        for i in range(len(nums)):\n",
    "            summ+=nums[i]\n",
    "            if summ-k in summ_dict:\n",
    "                ans=max(ans,i-summ_dict[summ-k])\n",
    "            if summ not in summ_dict:\n",
    "                summ_dict[summ]=i\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        prefixsum=0\n",
    "        result=0\n",
    "        foundvalue={}\n",
    "        foundvalue[0]=-1\n",
    "        for i in range(len(nums)):\n",
    "            prefixsum+=nums[i]\n",
    "            if prefixsum not in foundvalue:\n",
    "                foundvalue[prefixsum]=i\n",
    "            if prefixsum-k in foundvalue:\n",
    "                result = max(result, i-foundvalue[prefixsum-k])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        # 前缀和，记录每个前缀和首次出现的位置\n",
    "        summ_dict={0:-1}\n",
    "        summ=0\n",
    "        ans=0\n",
    "        for i in range(len(nums)):\n",
    "            summ+=nums[i]\n",
    "            if summ-k in summ_dict:\n",
    "                ans=max(ans,i-summ_dict[summ-k])\n",
    "            if summ not in summ_dict:\n",
    "                summ_dict[summ]=i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        #不能用滑窗,因为有负数\n",
    "        #哈希+前缀和,因为要求子数组最长,相同前缀和只保留最早的一个\n",
    "        to={0:-1}\n",
    "        pre,ans=0,0\n",
    "        for i,x in enumerate(nums):\n",
    "            pre+=x\n",
    "            if pre-k in to:\n",
    "                ans=max(ans,i-to[pre-k])\n",
    "            if pre not in to:\n",
    "                to[pre]=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:   \n",
    "        f = {}\n",
    "        f[0] = -1\n",
    "\n",
    "        presum = 0\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            presum += nums[i]\n",
    "            if presum - k in f:\n",
    "                ans = max(ans, i - f[presum - k])\n",
    "            \n",
    "            if presum not in f:\n",
    "                f[presum] = i\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        count=0\n",
    "        dp={0:-1}\n",
    "        ret=0\n",
    "        for i in range(len(nums)):\n",
    "            count+=nums[i]\n",
    "            if count not in dp:\n",
    "                dp[count]=i\n",
    "            if count-k in dp:\n",
    "                ret=max(ret,i-dp[count-k])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        prefix = {0: -1}\n",
    "        cur_total = 0\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            cur_total += nums[i]\n",
    "            if cur_total - k in prefix:\n",
    "                ans = max(ans, i - prefix[cur_total - k])\n",
    "            if cur_total not in prefix:\n",
    "                prefix[cur_total] = i\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # res = 0\n",
    "        # dic = {}\n",
    "        # for i in range(n):\n",
    "        #     # SUM = 0\n",
    "        #     for j in range(i,n):\n",
    "        #         t = k - nums[j]\n",
    "        #         if t in dic:\n",
    "        #             res = max(res, dic[t]+1)\n",
    "        #         dic[t] = j-i\n",
    "        #         # SUM += nums[j]\n",
    "        #         # if SUM == k:\n",
    "        #         #     res = max(res,j-i+1)\n",
    "        # return res\n",
    "        \n",
    "        # res = 0\n",
    "        # prefix = [0]*(n+1)\n",
    "        # for i in range(n):\n",
    "        #     prefix[i+1] = prefix[i]+nums[i]\n",
    "        # for i in range(n+1):\n",
    "        #     for j in range(i,n+1):\n",
    "        #         if prefix[j]-prefix[i]==k:\n",
    "        #             res = max(res, j-i)\n",
    "        # return res\n",
    "\n",
    "        res = 0\n",
    "        dic = {}\n",
    "        dic[0] = -1\n",
    "        prefix = 0\n",
    "        for i in range(n):\n",
    "            prefix += nums[i]\n",
    "            t = prefix - k\n",
    "            if t in dic:\n",
    "                res = max(res, i-dic[t])\n",
    "            if prefix not in dic:\n",
    "                dic[prefix] = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        lookup = {}\n",
    "        cur_len, res = 0, 0\n",
    "        prefix_sum = 0\n",
    "        for i in range(len(nums)):\n",
    "            prefix_sum += nums[i]\n",
    "            if prefix_sum == k:\n",
    "                res = i + 1\n",
    "            elif prefix_sum - k in lookup:\n",
    "                res = max(res, i - lookup[prefix_sum-k])\n",
    "            if prefix_sum not in lookup:\n",
    "                lookup[prefix_sum] = i\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        # 前缀和，记录每个前缀和首次出现的位置\n",
    "        summ_dict={0:-1}\n",
    "        summ=0\n",
    "        ans=0\n",
    "        for i in range(len(nums)):\n",
    "            summ+=nums[i]\n",
    "            if summ-k in summ_dict:\n",
    "                ans=max(ans,i-summ_dict[summ-k])\n",
    "            if summ not in summ_dict:\n",
    "                summ_dict[summ]=i\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        psumdict = {}\n",
    "        cursum = 0\n",
    "        ans = 0\n",
    "        psumdict[0] = -1 \n",
    "        for index, num in enumerate(nums):\n",
    "            cursum += num\n",
    "            if cursum not in psumdict:\n",
    "                psumdict[cursum] =  index\n",
    "            if cursum - k in psumdict:\n",
    "                ans = max(ans, index - psumdict[cursum - k] )\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        hashmap = {}\n",
    "        running_sum = 0\n",
    "        hashmap[0] = -1\n",
    "        max_len = 0\n",
    "        \n",
    "        for index, num in enumerate(nums):\n",
    "            running_sum += num\n",
    "            if running_sum - k in hashmap:\n",
    "                max_len = max(max_len, index - hashmap[running_sum - k])\n",
    "            if running_sum not in hashmap:\n",
    "                hashmap[running_sum] = index\n",
    "                \n",
    "        return max_len\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        m = dict()\n",
    "        sums = 0\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            sums += nums[i]\n",
    "\n",
    "            if sums - k in m:\n",
    "                ans = max(ans, i - m[sums - k])\n",
    "\n",
    "            if sums == k:\n",
    "                ans = max(ans, i + 1)\n",
    "\n",
    "            if sums not in m:\n",
    "                m[sums] = i\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        pre_sum_dict = {0: -1}\n",
    "        accumulate_val = 0\n",
    "        candidates = []\n",
    "\n",
    "        for i, val in enumerate(nums):\n",
    "            accumulate_val += val\n",
    "            need_val = accumulate_val - k\n",
    "            if need_val in pre_sum_dict:\n",
    "                candidates.append(i - pre_sum_dict[need_val])\n",
    "            if not accumulate_val in pre_sum_dict:\n",
    "                pre_sum_dict[accumulate_val] = i\n",
    "        \n",
    "        if candidates:\n",
    "            return max(candidates)\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        # prefixsum + hashtable\n",
    "        prefixsum = 0\n",
    "        length = 0  \n",
    "        indices = {} #store the value of prefixsum and its index\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            prefixsum += nums[i]\n",
    "            if prefixsum not in indices.keys():\n",
    "                indices[prefixsum] = i #key is the prefixsum, value is the index\n",
    "\n",
    "            if prefixsum == k:  #数组从0到i的和等于k\n",
    "                length = i+1\n",
    "            if prefixsum - k in indices.keys():\n",
    "                length = max(length, i - indices[prefixsum - k]) #数组从indices[prefixsum - k]+1 到i 的和等于k\n",
    "\n",
    "        return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        '记录prefix和prefix的下标，如果遇到prefix-k在dict中说明 prefix[j]-prefix[i] = k'\n",
    "\n",
    "        dic = {0:-1}    # {prefix: idx}\n",
    "        max_len = prefix = 0\n",
    "        for i in range(len(nums)):\n",
    "            prefix += nums[i]\n",
    "            if prefix - k in dic and i - dic[prefix - k] > max_len:\n",
    "                max_len = i - dic[prefix - k]\n",
    "            if prefix not in dic:\n",
    "                dic[prefix] = i\n",
    "        return max_len\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:   \n",
    "        hashmap = {0: -1}            # f(value) = idx\n",
    "\n",
    "        presum = 0\n",
    "        ans = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            presum += num\n",
    "            if presum - k in hashmap:\n",
    "                ans = max(ans, i - hashmap[presum - k])\n",
    "        \n",
    "            if presum not in hashmap:\n",
    "                hashmap[presum] = i\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        # dic stores prefix_sums of subarrays ending at some pos i and starting at the head\n",
    "        dic = {0: -1}\n",
    "        temp = 0\n",
    "        result = 0\n",
    "        for i in range(len(nums)):\n",
    "            temp += nums[i]\n",
    "            if temp - k in dic:\n",
    "                result = max(result, i - dic[temp - k])\n",
    "            if temp not in dic:\n",
    "                dic[temp] = i\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        pre_sum = {0: -1}\n",
    "        accumulate_val = 0\n",
    "        ret_val = 0\n",
    "        for idx, val in enumerate(nums):\n",
    "            accumulate_val += val\n",
    "            need_pre_val = accumulate_val - k\n",
    "            if need_pre_val in pre_sum:\n",
    "                ret_val = max(idx - pre_sum[need_pre_val], ret_val)\n",
    "            if accumulate_val not in pre_sum:\n",
    "                pre_sum[accumulate_val] = idx\n",
    "        return ret_val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        mp = {0: -1}\n",
    "        sum = 0\n",
    "        maxLen = 0\n",
    "        for i in range(len(nums)):\n",
    "            sum += nums[i]\n",
    "            if sum == k:\n",
    "                maxLen = i + 1\n",
    "            elif sum - k in mp:\n",
    "                maxLen = max(maxLen, i - mp[sum - k])\n",
    "            if sum not in mp:\n",
    "                mp[sum] = i\n",
    "        return maxLen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        '记录prefix和prefix的下标，如果遇到prefix-k在dict中说明 prefix[j]-prefix[i] = k'\n",
    "\n",
    "        dic = {0:-1}\n",
    "        max_len = prefix = 0\n",
    "        for i in range(len(nums)):\n",
    "            prefix += nums[i]\n",
    "            if prefix - k in dic and i - dic[prefix - k] > max_len:\n",
    "                max_len = i - dic[prefix - k]\n",
    "            if prefix not in dic:\n",
    "                dic[prefix] = i\n",
    "        return max_len\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        prefix = {}\n",
    "        prefix[0] = 0\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            s += nums[i]\n",
    "            if (s - k) in prefix.keys():\n",
    "                ans = max(ans, i + 1 - prefix[s - k])\n",
    "            if s not in prefix.keys():\n",
    "                prefix[s] = i+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        # right_sum - left_sum = k\n",
    "        # right_sum - k = left_sum\n",
    "\n",
    "        # 利用prefix\n",
    "        # -----------------\n",
    "        # | prefix - k | k |\n",
    "        # | prefix         | \n",
    "\n",
    "        # nums     1  1 -1 5 -2 3\n",
    "        # prefix   0  1 2  1 6  4 7\n",
    "        #          -1 0 1 过 3  4 5 \n",
    "        # 最开始加入0的目的：表示空前缀，当total刚好=k时，确保没有差的   \n",
    "        prefix = {0: -1}\n",
    "        cur_total = 0\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            cur_total += nums[i]\n",
    "            # 寻找max size\n",
    "            if cur_total - k in prefix:\n",
    "                ans = max(ans, i - prefix[cur_total - k])\n",
    "            # 找最大：只记录一个数第一次出现的位置\n",
    "            if cur_total not in prefix:\n",
    "                prefix[cur_total] = i\n",
    "        return ans\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        # 前缀和，记录每个前缀和首次出现的位置\n",
    "        summ_dict={0:-1}\n",
    "        summ=0\n",
    "        ans=0\n",
    "        for i in range(len(nums)):\n",
    "            summ+=nums[i]\n",
    "            if summ-k in summ_dict:\n",
    "                ans=max(ans,i-summ_dict[summ-k])\n",
    "            if summ not in summ_dict:\n",
    "                summ_dict[summ]=i\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        preSum = [0] * (n + 1)\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            preSum[i] = preSum[i - 1] + nums[i - 1]\n",
    "\n",
    "        hashmap = {}\n",
    "\n",
    "        res = 0 \n",
    "        for i in range(n + 1):\n",
    "            if preSum[i] not in hashmap:\n",
    "                hashmap[preSum[i]] = i\n",
    "            if (j := preSum[i] - k) in hashmap:\n",
    "                res = max(res, i - hashmap[j])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        # nums, k = [4,1,1,1,1,2], 4\n",
    "        pre = 0\n",
    "        dic = {0: -1}\n",
    "        max_len = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            pre += num\n",
    "            if pre - k in dic:\n",
    "                max_len = max(max_len, i - dic[pre - k])\n",
    "            if pre not in dic: # 记录第一次出现的位置\n",
    "                dic[pre] = i\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        dct = dict()\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        dct[0] = -1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            pre += nums[i]\n",
    "            if pre - k in dct and i - dct[pre - k] > ans:\n",
    "                ans = i - dct[pre - k]\n",
    "            if pre not in dct:\n",
    "                dct[pre] = i\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        prefix_sum = 0\n",
    "        longest_subarray = 0\n",
    "        indices = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            prefix_sum += num \n",
    "            \n",
    "            # 检查是否存在累加和等于k的子数组\n",
    "            if prefix_sum == k:\n",
    "                longest_subarray = i + 1\n",
    "                \n",
    "            # 如果之前出现过累加和等于prefix_sum - k的位置\n",
    "            # 则更新最长子数组长度\n",
    "            if prefix_sum - k in indices:\n",
    "                longest_subarray = max(longest_subarray, i - indices[prefix_sum - k])\n",
    "                \n",
    "            # 仅当当前前缀和不在字典中时，将其添加到字典中\n",
    "            if prefix_sum not in indices:\n",
    "                indices[prefix_sum] = i\n",
    "        \n",
    "        return longest_subarray"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        presum = 0\n",
    "        ans = 0\n",
    "        summap = {0: -1}\n",
    "        for i, num in enumerate(nums):\n",
    "            presum += num\n",
    "            if presum - k in summap:\n",
    "                ans = max(ans, i - summap[presum - k])\n",
    "            if presum not in summap:\n",
    "                summap[presum] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        preSum = 0\n",
    "        hashtable = {0:-1}\n",
    "        maxLen = 0\n",
    "\n",
    "        for i,num in enumerate(nums):\n",
    "            preSum += num\n",
    "            if preSum - k in hashtable:\n",
    "                maxLen = max(i-hashtable[preSum - k], maxLen)\n",
    "            if preSum not in hashtable:\n",
    "                hashtable[preSum] = i\n",
    "            \n",
    "        return maxLen\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        # 联系的\n",
    "        m = {0: -1}\n",
    "        s = ans = 0\n",
    "        for i, c in enumerate(nums):\n",
    "            s += c\n",
    "            if s - k in m:\n",
    "                ans = max(ans, i - m[s-k])\n",
    "            if s not in m:\n",
    "                m[s] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        my_dict = dict()\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        my_dict[0] = -1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            pre +=nums[i]\n",
    "            if pre - k in my_dict and i-my_dict[pre-k] > ans:\n",
    "                ans = i - my_dict[pre-k]\n",
    "            if pre not in my_dict:\n",
    "                my_dict[pre] = i\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        prefix_sum=0\n",
    "        longest_subarray=0\n",
    "        indices={}\n",
    "        for i, num in enumerate(nums):\n",
    "            prefix_sum+=num\n",
    "\n",
    "            if prefix_sum == k:\n",
    "                longest_subarray = i+1\n",
    "            \n",
    "            if prefix_sum-k in indices:\n",
    "                longest_subarray = max(longest_subarray, i-indices[prefix_sum-k])\n",
    "            \n",
    "            if prefix_sum not in indices:\n",
    "                indices[prefix_sum]=i\n",
    "\n",
    "        return longest_subarray"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        preSum = collections.defaultdict()\n",
    "        preSum[0] = 0\n",
    "        cur = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            cur += nums[i]\n",
    "            if cur not in preSum:\n",
    "                preSum[cur] = i + 1\n",
    "\n",
    "            if cur - k in preSum:\n",
    "                ans = max(i - preSum[cur-k] + 1, ans)\n",
    "            \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        dct=dict()\n",
    "        n=len(nums)\n",
    "        pre=0\n",
    "        dct[0]=-1\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            pre+=nums[i]\n",
    "            if pre-k in dct and i-dct[pre-k]>ans:\n",
    "                ans=i-dct[pre-k]\n",
    "            if pre not in dct:\n",
    "                dct[pre]=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        s = 0\n",
    "        cache = {0: -1}\n",
    "        for i, n in enumerate(nums):\n",
    "            s += n\n",
    "            if s - k in cache:\n",
    "                res = max(res, i - cache[s - k])\n",
    "            # s不在cache里时才更新\n",
    "            if s not in cache:\n",
    "                cache[s] = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        cumsum = [0] * (n+1)\n",
    "        pos = {}\n",
    "        ans = 0\n",
    "        pos[0] = 0\n",
    "        for i in range(1, n+1):\n",
    "            cumsum[i] = cumsum[i-1] + nums[i-1]\n",
    "            if cumsum[i] not in pos:\n",
    "                pos[cumsum[i]] = i\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            oppo = cumsum[i]-k\n",
    "            if oppo in pos:\n",
    "                ans = max(ans, i-pos[oppo])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        dp = {0:-1}\n",
    "        c = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            c += num\n",
    "            if c - k in dp:\n",
    "                ans = max(ans, i-dp[c-k])\n",
    "            if c not in dp:\n",
    "                dp[c] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        sums = [0] * n\n",
    "        dist = {0: -1}\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                sums[0] = nums[0]\n",
    "            else:\n",
    "                sums[i] = sums[i - 1] + nums[i]\n",
    "            \n",
    "            if sums[i] - k in dist:\n",
    "                res = max(res, i - dist[sums[i] - k])\n",
    "                #print(i, dist[sums[i] - k])\n",
    "            if sums[i] not in dist:\n",
    "                dist[sums[i]] = i\n",
    "        \n",
    "        #print(sums)\n",
    "        #print(dist)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        prefix = [0] * (len(nums)+1)\n",
    "        curval = 0\n",
    "        for i in range(len(nums)):\n",
    "            curval += nums[i]\n",
    "            prefix[i+1] = curval\n",
    "        lookup = {}\n",
    "        ans = 0\n",
    "        for id, num in enumerate(prefix):\n",
    "            if (num - k) in lookup.keys():\n",
    "                ans = max(ans, id - lookup[num-k])\n",
    "            if num not in lookup:\n",
    "                lookup[num] = id\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        acc = list(accumulate(nums, initial=0))\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        for i, j in enumerate(acc):\n",
    "            if j - k in cnt:\n",
    "                ans = max(ans, i - cnt[j - k]) \n",
    "            if j in cnt:\n",
    "                continue\n",
    "            cnt[j] = i \n",
    "        return ans \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        prefix_sum = 0\n",
    "        longest_subarray = 0\n",
    "        indices = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            prefix_sum += num \n",
    "            \n",
    "            # 检查是否存在累加和等于k的子数组\n",
    "            if prefix_sum == k:\n",
    "                longest_subarray = i + 1\n",
    "                \n",
    "            # 如果之前出现过累加和等于prefix_sum - k的位置\n",
    "            # 则更新最长子数组长度\n",
    "            if prefix_sum - k in indices:\n",
    "                longest_subarray = max(longest_subarray, i - indices[prefix_sum - k])\n",
    "                \n",
    "            # 仅当当前前缀和不在字典中时，将其添加到字典中\n",
    "            if prefix_sum not in indices:\n",
    "                indices[prefix_sum] = i\n",
    "        \n",
    "        return longest_subarray\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        #不能用滑窗,因为有负数\n",
    "        #哈希+前缀和,因为要求子数组最长,相同前缀和只保留最早的一个\n",
    "        to={0:-1}\n",
    "        pre,ans=0,0\n",
    "        for i,x in enumerate(nums):\n",
    "            pre+=x\n",
    "            if pre-k in to:\n",
    "                ans=max(ans,i-to[pre-k])\n",
    "            if pre not in to:\n",
    "                to[pre]=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        preSum = 0\n",
    "        h = {}\n",
    "        h[0] = -1\n",
    "        ans = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            preSum += num\n",
    "            if preSum - k in h:\n",
    "                ans = max(ans, right - h.get(preSum - k))\n",
    "            if preSum not in h:\n",
    "                h[preSum] = right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        cumsum = [0] * (n+1)\n",
    "        pos = {}\n",
    "        ans = 0\n",
    "        pos[0] = 0\n",
    "        for i in range(1, n+1):\n",
    "            cumsum[i] = cumsum[i-1] + nums[i-1]\n",
    "            if cumsum[i] not in pos:\n",
    "                pos[cumsum[i]] = i\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            if cumsum[i]-k in pos:\n",
    "                ans = max(ans, i-pos[cumsum[i]-k])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        dic = {0:-1}\n",
    "        cur = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            cur += num\n",
    "            # if cur == k:\n",
    "            #     res = i + 1\n",
    "            if cur - k in dic:\n",
    "                res = max(res, i - dic[cur - k])\n",
    "            if cur not in dic:\n",
    "                dic[cur] = i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        preSums = {0: -1}\n",
    "        curPreSum = 0\n",
    "        maxLen = 0\n",
    "\n",
    "        for idx, num in enumerate(nums):\n",
    "            curPreSum += num\n",
    "            target = curPreSum - k\n",
    "            \n",
    "            if target in preSums:\n",
    "                maxLen = max(maxLen, idx - preSums[target])\n",
    "            if curPreSum not in preSums:\n",
    "                preSums[curPreSum] = idx\n",
    "        \n",
    "        return maxLen\n",
    "\n",
    "'''\n",
    "k = 3\n",
    "[1,2,1]\n",
    "\n",
    "preSums = {0:0, 1:0}\n",
    "1, 2\n",
    "3, 0\n",
    "\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        preSum = dict()\n",
    "        preSum[0] = -1\n",
    "        presum = [0]\n",
    "        s = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            s += v\n",
    "            presum.append(s)\n",
    "            if s not in preSum:\n",
    "                preSum[s] = i\n",
    "        res = 0\n",
    "        for p in range(len(nums), -1, -1):\n",
    "            if presum[p] - k in preSum:\n",
    "                res = max(res, p - preSum[presum[p] - k]-1)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        cumsum = [0]\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            cumsum.append(cumsum[-1]+nums[i])\n",
    "        record = defaultdict(int)\n",
    "        max_length = 0\n",
    "        record[0] = 0\n",
    "        \n",
    "        for i in range(1,n+1):\n",
    "            if cumsum[i]-k in record:\n",
    "                max_length = max(max_length, i-record[cumsum[i]-k])\n",
    "            if cumsum[i] not in record:\n",
    "                record[cumsum[i]] = i\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        pre = list(accumulate(nums, initial = 0))\n",
    "        n = len(nums)\n",
    "        m = {}\n",
    "        m[0] = -1\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            v = pre[i + 1]\n",
    "            d = v - k\n",
    "            if nums[i] == k:\n",
    "                res = max(res, 1)\n",
    "            if d in m:\n",
    "                res = max(res, i - m[d])\n",
    "            if v not in m:\n",
    "                m[v] = i\n",
    "        return res\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        hashmap = {}\n",
    "        running_sum = 0\n",
    "        hashmap[0] = -1\n",
    "        max_len = 0\n",
    "        \n",
    "        for index, num in enumerate(nums):\n",
    "            running_sum += num\n",
    "            if running_sum - k in hashmap:\n",
    "                max_len = max(max_len, index - hashmap[running_sum - k])\n",
    "            if running_sum not in hashmap:\n",
    "                hashmap[running_sum] = index\n",
    "                \n",
    "        return max_len\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        cumsum = [0]\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            cumsum.append(cumsum[-1]+nums[i])\n",
    "        record = defaultdict(int)\n",
    "        max_length = 0\n",
    "        record[0] = 0\n",
    "        \n",
    "        for i in range(1,n+1):\n",
    "            if cumsum[i]-k in record:\n",
    "                max_length = max(max_length, i-record[cumsum[i]-k])\n",
    "            if cumsum[i] not in record:\n",
    "                record[cumsum[i]] = i\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        curSum = 0\n",
    "        # sum of a[0]...a[i], i.e. the first i elems: i\n",
    "        prefix = {0: 0}\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            curSum += nums[i]\n",
    "            if curSum - k in prefix.keys():\n",
    "                # prefix[curSum - k]: j, means sum of the first j elems, i.e. a[0]...a[j-1], is prefix[curSum - k]\n",
    "                # sum of a[j]...a[i] is k. Length of the array is i - j + 1\n",
    "                res = max(res, i - prefix[curSum - k] + 1)\n",
    "            if curSum not in prefix.keys():\n",
    "                # curSum is the sum of the first i + 1 elems\n",
    "                prefix[curSum] = i + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        preSums = {}\n",
    "        curPreSum = 0\n",
    "        maxLen = 0\n",
    "\n",
    "        for idx, num in enumerate(nums):\n",
    "            curPreSum += num\n",
    "            target = curPreSum - k\n",
    "            if target == 0:\n",
    "                maxLen = max(maxLen, idx + 1)\n",
    "            elif target in preSums:\n",
    "                maxLen = max(maxLen, idx - preSums[target])\n",
    "            if curPreSum not in preSums:\n",
    "                preSums[curPreSum] = idx\n",
    "        \n",
    "        return maxLen\n",
    "\n",
    "'''\n",
    "k = 3\n",
    "[1,2,1]\n",
    "\n",
    "preSums = {0:0, 1:0}\n",
    "1, 2\n",
    "3, 0\n",
    "\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        sums = [0] * len(nums)\n",
    "        dist = {0: -1}\n",
    "        res = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if i == 0:\n",
    "                sums[0] = num\n",
    "            else:\n",
    "                sums[i] = sums[i - 1] + num\n",
    "            \n",
    "            if (t := sums[i] - k) in dist:\n",
    "                res = max(res, i - dist[t])\n",
    "                #print(i, dist[sums[i] - k])\n",
    "            if sums[i] not in dist:\n",
    "                dist[sums[i]] = i\n",
    "        \n",
    "        #print(sums)\n",
    "        #print(dist)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        hashmap = {}\n",
    "        running_sum = 0\n",
    "        hashmap[0] = -1\n",
    "        max_len = 0\n",
    "        \n",
    "        for index, num in enumerate(nums):\n",
    "            running_sum += num\n",
    "            if running_sum - k in hashmap:\n",
    "                max_len = max(max_len, index - hashmap[running_sum - k])\n",
    "            if running_sum not in hashmap:\n",
    "                hashmap[running_sum] = index\n",
    "                \n",
    "        return max_len\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre_sum = 0\n",
    "        ans = 0 \n",
    "        pre_sum_idx = {}\n",
    "        pre_sum_idx[0] = -1\n",
    "        for i in range(n):\n",
    "            pre_sum += nums[i]\n",
    "            if not pre_sum in pre_sum_idx:\n",
    "                pre_sum_idx[pre_sum] = i\n",
    "            \n",
    "            if pre_sum - k in pre_sum_idx:\n",
    "                ans = max(ans, i - pre_sum_idx[pre_sum - k])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        # 创建一个字典，用于存储前缀和及其对应的下标\n",
    "        num2index = dict()\n",
    "\n",
    "        # 初始化最长子数组的长度为0\n",
    "        max_length = 0\n",
    "\n",
    "        # 初始化前缀和为0\n",
    "        prefix_sum = 0\n",
    "\n",
    "        # 遍历数组\n",
    "        for i in range(len(nums)):\n",
    "            # 计算当前的前缀和\n",
    "            prefix_sum += nums[i]\n",
    "\n",
    "            # 如果当前的前缀和等于目标值k，则更新最长子数组的长度\n",
    "            if prefix_sum == k:\n",
    "                max_length = i + 1  # 因为是从第一个元素开始的，所以长度是 i+1\n",
    "\n",
    "            # 检查当前前缀和减去目标值k是否在字典中\n",
    "            if prefix_sum - k in num2index.keys():\n",
    "                # 如果在字典中，说明找到了一个和为k的子数组\n",
    "                # 更新最长子数组的长度\n",
    "                max_length = max(max_length, i - num2index[prefix_sum - k])\n",
    "\n",
    "            # 如果当前的前缀和不在字典中，则将其添加到字典中\n",
    "            # 注意：我们只记录第一次出现该前缀和的下标\n",
    "            if prefix_sum not in num2index.keys():\n",
    "                num2index[prefix_sum] = i\n",
    "\n",
    "        # 返回找到的最长子数组的长度\n",
    "        return max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        prefixsum = 0\n",
    "        longest = 0\n",
    "        indices = {}\n",
    "        l = len(nums)\n",
    "        if l == 0:\n",
    "            return 0\n",
    "        elif l == 1:\n",
    "            if nums[0] == k:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        for i in range(l):\n",
    "            prefixsum += nums[i]\n",
    "            if prefixsum == k:\n",
    "                if longest <= (i + 1):\n",
    "                    longest = i + 1\n",
    "            if prefixsum - k in indices:\n",
    "                index = indices[prefixsum - k]\n",
    "                if i - index >= longest:\n",
    "                    longest = i - index\n",
    "            if prefixsum not in indices:\n",
    "                indices[prefixsum] = i\n",
    "        return longest\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre_sum = 0\n",
    "        ans = 0 \n",
    "        pre_sum_idx = {}\n",
    "        pre_sum_idx[0] = -1\n",
    "        for i in range(n):\n",
    "            pre_sum += nums[i]\n",
    "            if not pre_sum in pre_sum_idx:   # important, always maitain the first occurance to ensure longest\n",
    "                pre_sum_idx[pre_sum] = i\n",
    "            \n",
    "            if pre_sum - k in pre_sum_idx:\n",
    "                ans = max(ans, i - pre_sum_idx[pre_sum - k])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        # 创建一个字典，用于存储前缀和及其对应的下标\n",
    "        num2index = dict()\n",
    "\n",
    "        # 初始化最长子数组的长度为0\n",
    "        max_length = 0\n",
    "\n",
    "        # 初始化前缀和为0\n",
    "        prefix_sum = 0\n",
    "\n",
    "        # 遍历数组\n",
    "        for i in range(len(nums)):\n",
    "            # 计算当前的前缀和\n",
    "            prefix_sum += nums[i]\n",
    "\n",
    "            # 如果当前的前缀和等于目标值k，则更新最长子数组的长度\n",
    "            if prefix_sum == k:\n",
    "                max_length = i + 1  # 因为是从第一个元素开始的，所以长度是 i+1\n",
    "\n",
    "            # 检查当前前缀和减去目标值k是否在字典中\n",
    "            if prefix_sum - k in num2index.keys():\n",
    "                # 如果在字典中，说明找到了一个和为k的子数组\n",
    "                # 更新最长子数组的长度\n",
    "                max_length = max(max_length, i - num2index[prefix_sum - k])\n",
    "\n",
    "            # 如果当前的前缀和不在字典中，则将其添加到字典中\n",
    "            # 注意：我们只记录第一次出现该前缀和的下标\n",
    "            if prefix_sum not in num2index.keys():\n",
    "                num2index[prefix_sum] = i\n",
    "\n",
    "        # 返回找到的最长子数组的长度\n",
    "        return max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        dct = dict()\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        dct[0] = -1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            pre += nums[i]\n",
    "            if pre - k in dct and i - dct[pre - k] > ans:\n",
    "                ans = i - dct[pre - k]\n",
    "            if pre not in dct:\n",
    "                dct[pre] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        sums = [0] * len(nums)\n",
    "        dist = {0: -1}\n",
    "        res = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if i == 0:\n",
    "                sums[0] = num\n",
    "            else:\n",
    "                sums[i] = sums[i - 1] + num\n",
    "            \n",
    "            if (t := sums[i] - k) in dist:\n",
    "                res = max(res, i - dist[t])\n",
    "                #print(i, dist[sums[i] - k])\n",
    "            if sums[i] not in dist:\n",
    "                dist[sums[i]] = i\n",
    "        \n",
    "        #print(sums)\n",
    "        #print(dist)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        sums = [0] * n\n",
    "        dist = {0: -1}\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                sums[0] = nums[0]\n",
    "            else:\n",
    "                sums[i] = sums[i - 1] + nums[i]\n",
    "            \n",
    "            if sums[i] - k in dist:\n",
    "                res = max(res, i - dist[sums[i] - k])\n",
    "                #print(i, dist[sums[i] - k])\n",
    "            if sums[i] not in dist:\n",
    "                dist[sums[i]] = i\n",
    "        \n",
    "        #print(sums)\n",
    "        #print(dist)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        presum = [0] * (n+1)\n",
    "        for i in range(1,n+1):\n",
    "            presum[i] = presum[i-1] + nums[i-1]\n",
    "        print(presum)\n",
    "        \n",
    "        # maxStr = 0\n",
    "        # for i in range(n+1):\n",
    "        #     for j in range(i, n+1):\n",
    "        #         if presum[j] - presum[i] == k:\n",
    "        #             maxStr = max(maxStr, (j-i))\n",
    "\n",
    "        # for i in range(n,-1,-1):\n",
    "        #     for j in range(0, n+1-i):\n",
    "        #         if presum[j+i] - presum[j] == k:\n",
    "        #             return i\n",
    "        maxStr = 0\n",
    "        d = {}\n",
    "        for i in range(1, n+1):\n",
    "            if presum[i] == k:\n",
    "                maxStr = i\n",
    "            if (presum[i] - k) in d:\n",
    "                maxStr = max(maxStr, i - d[presum[i] - k])\n",
    "            if presum[i] not in d:\n",
    "                d[presum[i]] = i\n",
    "            \n",
    "        return maxStr\n",
    "            \n",
    "        return 0\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        d = {}\n",
    "        pre = 0\n",
    "        longest = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            pre += num\n",
    "            if pre == k:\n",
    "                longest = i+1\n",
    "            if pre-k in d:\n",
    "                longest = max(longest, i-d[pre-k])\n",
    "            if pre not in d:\n",
    "                d[pre] = i\n",
    "        return longest\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums)==1:\n",
    "            if k==nums[0]:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        line=[0]\n",
    "        for idt in range(len(nums)-1):\n",
    "            line.append(line[-1]+nums[idt])\n",
    "\n",
    "        d=set([0])\n",
    "        dic={0:0}\n",
    "        if k in nums:\n",
    "            length=1\n",
    "        else:\n",
    "            length=float(\"-inf\")\n",
    "        for idt in range(len(nums)):\n",
    "            b=line[idt]\n",
    "            x=nums[idt]\n",
    "            if b+x-k in d:\n",
    "                length=max(length,idt-dic[b+x-k]+1)\n",
    "            if b not in d:\n",
    "                d.add(b)\n",
    "                dic[b]=idt\n",
    "        if length==float(\"-inf\"):\n",
    "            return 0\n",
    "        return length\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        len_n = len(nums)\n",
    "        prefix_dict = defaultdict(list)\n",
    "        prefix_dict[0].append(0)\n",
    "        prefix_dict[nums[0]].append(1)\n",
    "\n",
    "        for idx in range(1,len_n):\n",
    "            nums[idx] += nums[idx-1]\n",
    "            prefix_dict[nums[idx]].append(idx+1)\n",
    "\n",
    "        max_gap = 0\n",
    "        for key in prefix_dict.keys():\n",
    "            if key + k not in prefix_dict:\n",
    "                continue\n",
    "            vals1 = prefix_dict[key]\n",
    "            vals2 = prefix_dict[key+k]\n",
    "            max_gap = max(max_gap, vals2[-1] - vals1[0])\n",
    "\n",
    "        print(prefix_dict)\n",
    "        return max_gap\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        prefixSum = {0:[-1]}\n",
    "        curr = 0\n",
    "        for i in range(len(nums)):\n",
    "            curr += nums[i]\n",
    "            if curr in prefixSum:\n",
    "                prefixSum[curr].append(i)\n",
    "            else:\n",
    "                prefixSum[curr] = [i, ]\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            s += nums[i]\n",
    "            require = s - k\n",
    "            if require in prefixSum:\n",
    "                ans = max(ans, i - prefixSum[require][0])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        presum = [0] * (len(nums) + 1)\n",
    "        for i, n in enumerate(nums):\n",
    "            presum[i + 1] = presum[i] + n\n",
    "\n",
    "        presum_dict = dict()\n",
    "        max_l = 0\n",
    "        for i, p in enumerate(presum):\n",
    "            \n",
    "            if p - k in presum_dict:\n",
    "                for m in presum_dict[p - k]:\n",
    "                    max_l = max(max_l, i - m)\n",
    "\n",
    "            presum_dict[p] = presum_dict[p] + [i] if p in presum_dict else [i]\n",
    "\n",
    "        return max_l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArrayLen(self, nums: List[int], k: int) -> int:\n",
    "        self.hashMap = collections.defaultdict(lambda:-1)\n",
    "        n = len(nums)\n",
    "        pre_sum = [0]*(n+1)\n",
    "        self.hashMap[0]=0\n",
    "        for i in range(1,n+1):\n",
    "            pre_sum[i]=pre_sum[i-1]+nums[i-1]\n",
    "            if self.hashMap[pre_sum[i]] == -1:\n",
    "                self.hashMap[pre_sum[i]]=i\n",
    "        #print(self.hashMap)\n",
    "        max_len = 0\n",
    "        for i in range(1,n+1):\n",
    "            idx = self.hashMap[pre_sum[i]-k] \n",
    "            if idx!=-1 and idx<i:\n",
    "                max_len = max(max_len,i-idx)\n",
    "        \n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        # 前缀和\n",
    "        def maxSubArray(nums: List[int]) -> int:\n",
    "            pre = min_pre = 0\n",
    "            ret = -inf\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                ret = max(ret, pre - min_pre)\n",
    "                min_pre = min(min_pre, pre)\n",
    "            return ret\n",
    "        ret = -inf\n",
    "        for i in range(1, len(arr)-1):\n",
    "            ret = max(ret, maxSubArray(arr[:i] + arr[i+1:]))\n",
    "        return max(ret, maxSubArray(arr))\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[0] * 2 for _ in range(n+1)]\n",
    "        dp[0] = [-inf] * 2\n",
    "        for i in range(n):\n",
    "            dp[i+1][0] = max(dp[i][0], 0) + arr[i]\n",
    "            dp[i+1][1] = max(dp[i][1] + arr[i], dp[i][0])\n",
    "        return max(max(x) for x in dp)\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        ret = dp0 = dp1 = -inf\n",
    "        for x in arr:\n",
    "            dp1 = max(dp1 + x, dp0)\n",
    "            dp0 = max(dp0, 0) + x\n",
    "            ret = max(ret, dp0, dp1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        # 前缀和\n",
    "        def maxSubArray(nums: List[int]) -> int:\n",
    "            pre = min_pre = 0\n",
    "            ret = -inf\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                ret = max(ret, pre - min_pre)\n",
    "                min_pre = min(min_pre, pre)\n",
    "            return ret\n",
    "        ret = -inf\n",
    "        for i in range(1, len(arr)-1):\n",
    "            ret = max(ret, maxSubArray(arr[:i] + arr[i+1:]))\n",
    "        return max(ret, maxSubArray(arr))\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[0] * 2 for _ in range(n+1)]\n",
    "        dp[0] = [-inf] * 2\n",
    "        for i in range(n):\n",
    "            dp[i+1][0] = max(dp[i][0], 0) + arr[i]\n",
    "            dp[i+1][1] = max(dp[i][1] + arr[i], dp[i][0])\n",
    "        return max(max(x) for x in dp)\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        ret = dp0 = dp1 = -inf\n",
    "        for x in arr:\n",
    "            dp1 = max(dp1 + x, dp0)\n",
    "            dp0 = max(dp0, 0) + x\n",
    "            ret = max(ret, dp0, dp1)\n",
    "        return ret\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        pre, beh = [0] * n, [0] * n\n",
    "        pre[0] = arr[0]\n",
    "        beh[-1] = arr[-1]\n",
    "        for i in range(1, n):\n",
    "            pre[i] = max(pre[i-1] + arr[i], arr[i])\n",
    "            beh[-1-i] = max(beh[-i] + arr[-1-i], arr[-1-i])\n",
    "        ret = max(pre)\n",
    "        for i in range(1, n-1):\n",
    "            ret = max(ret, pre[i-1] + beh[i+1])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        # 前缀和\n",
    "        def maxSubArray(nums: List[int]) -> int:\n",
    "            pre = min_pre = 0\n",
    "            ret = -inf\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                ret = max(ret, pre - min_pre)\n",
    "                min_pre = min(min_pre, pre)\n",
    "            return ret\n",
    "        ret = -inf\n",
    "        for i in range(1, len(arr)-1):\n",
    "            ret = max(ret, maxSubArray(arr[:i] + arr[i+1:]))\n",
    "        return max(ret, maxSubArray(arr))\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[0] * 2 for _ in range(n+1)]\n",
    "        dp[0] = [-inf] * 2\n",
    "        for i in range(n):\n",
    "            dp[i+1][0] = max(dp[i][0], 0) + arr[i]\n",
    "            dp[i+1][1] = max(dp[i][1] + arr[i], dp[i][0])\n",
    "        return max(max(x) for x in dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        max_sum = nums[0]\n",
    "        current_sum = nums[0]\n",
    "        for i in nums[1:]:\n",
    "            current_sum = max(i, current_sum + i)\n",
    "            max_sum = max(current_sum, max_sum)\n",
    "            print(i,current_sum, max_sum)\n",
    "        return max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums):\n",
    "        sum = nums[0]\n",
    "        result = sum\n",
    "        for num in nums[1:]:\n",
    "            if num < 0 and result < sum:\n",
    "                result = sum\n",
    "            sum = max(sum + num, num)\n",
    "        if result < sum:\n",
    "            result = sum\n",
    "        return result\n",
    "                \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums):\n",
    "        sum = nums[0]\n",
    "        result = sum\n",
    "        for num in nums[1:]:\n",
    "            if num < 0 and result < sum:\n",
    "                result = sum\n",
    "            sum = num if sum < 0 else sum + num\n",
    "        return max(result, sum)\n",
    "                \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i-1] > 0:\n",
    "                nums[i] += nums[i-1]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef maxSubArray(self, nums):\n",
    "\t\t\"\"\"\n",
    "\t\t:type nums: List[int]\n",
    "\t\t:rtype: int\n",
    "\t\t\"\"\"\n",
    "\n",
    "\t\tmax_sum = None\n",
    "\t\ttmp_sum = 0\n",
    "\t\tfor num in nums:\n",
    "\t\t\ttmp_sum += num\n",
    "\t\t\tif max_sum is None or tmp_sum > max_sum:\n",
    "\t\t\t\tmax_sum = tmp_sum\n",
    "\t\t\tif tmp_sum < 0:\n",
    "\t\t\t\ttmp_sum = 0\n",
    "\n",
    "\t\treturn max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef maxSubArray(self, nums):\n",
    "\t\t\"\"\"\n",
    "\t\t:type nums: List[int]\n",
    "\t\t:rtype: int\n",
    "\t\t\"\"\"\n",
    "\n",
    "\t\tmax_sum = None\n",
    "\t\ttmp_sum = 0\n",
    "\t\tfor num in nums:\n",
    "\t\t\ttmp_sum += num\n",
    "\t\t\tprint(num, tmp_sum)\n",
    "\t\t\tif max_sum is None or tmp_sum > max_sum:\n",
    "\t\t\t\tmax_sum = tmp_sum\n",
    "\t\t\tif tmp_sum < 0:\n",
    "\t\t\t\ttmp_sum = 0\n",
    "\n",
    "\t\treturn max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dp = [nums[0]]*len(nums)\n",
    "        \n",
    "        for i in range(1,len(nums)):\n",
    "            if dp[i-1] > 0:\n",
    "                dp[i] = dp[i-1] +nums[i]\n",
    "            else:\n",
    "                dp[i] = nums[i]\n",
    "        print(dp)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        a = {}\n",
    "        a[0] = nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            a[i] = max(a[i-1]+nums[i],nums[i])\n",
    "        index = max(a,key = a.get)\n",
    "        return a[index]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        leftlist=[]\n",
    "        rightlist=[]\n",
    "        if n==1:\n",
    "            return nums[0]\n",
    "        else:\n",
    "            leftnums=nums[0:n//2]\n",
    "            rightnums=nums[n//2:n]\n",
    "            leftbordersum=nums[n//2-1]\n",
    "            leftsum=nums[n//2-1]\n",
    "            rightbordersum=nums[n//2]\n",
    "            rightsum=nums[n//2]\n",
    "            for i in range(n//2-2,-1,-1):\n",
    "                leftsum=leftsum+nums[i]\n",
    "                if leftsum>leftbordersum:\n",
    "                    leftbordersum=leftsum\n",
    "            for i in range(1,(n+1)//2,1):\n",
    "                rightsum=rightsum+rightnums[i]\n",
    "                if rightsum>rightbordersum:\n",
    "                    rightbordersum=rightsum\n",
    "            allmax=rightbordersum+leftbordersum\n",
    "            return max([allmax,self.maxSubArray(leftnums),self.maxSubArray(rightnums)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums_length = len(nums)\n",
    "\n",
    "        max_total_dict = {}\n",
    "\n",
    "        for i in range(nums_length):\n",
    "            if i == 0:\n",
    "                max_total_dict[i] = nums[i]\n",
    "                continue\n",
    "\n",
    "            max_total_dict[i] = max(nums[i], nums[i] + max_total_dict[i - 1])\n",
    "        # print(max_total_dict)\n",
    "        return max(max_total_dict.values())\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: 'List[int]') -> 'int':\n",
    "        # Max = nums[0]\n",
    "        # for i in range(len(nums)):\n",
    "        #     v = 0\n",
    "        #     for j in range(i,len(nums)):\n",
    "        #         v = v+ nums[j]\n",
    "        #         if v>Max:\n",
    "        #             Max=v\n",
    "        # return Max\n",
    "        Max = max(nums)\n",
    "        temp_sum = 0\n",
    "        for i in range(len(nums)):\n",
    "            temp_sum = temp_sum+nums[i]\n",
    "            if temp_sum>Max:\n",
    "                Max = temp_sum\n",
    "            elif temp_sum<0:\n",
    "                temp_sum = 0\n",
    "        return Max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        sum = nums[0]\n",
    "        maxSum = sum\n",
    "        for i in range(1, len(nums)):\n",
    "            sum += nums[i]\n",
    "            if sum < nums[i]:\n",
    "                sum = nums[i]\n",
    "            maxSum = max(maxSum, sum)\n",
    "        return maxSum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        maxleft = self.maxSubArray(nums[0:len(nums)//2])\n",
    "        maxright = self.maxSubArray(nums[len(nums)//2:])\n",
    "        tmp = 0\n",
    "        maxl = nums[len(nums)//2-1]\n",
    "        \n",
    "        # 从左半边的最右边开始加，找最长子列和\n",
    "        for i in range(len(nums)//2-1,-1,-1):\n",
    "            tmp += nums[i]\n",
    "            maxl = max(tmp,maxl)\n",
    "    \n",
    "        # 从右半边的最左边开始加，找最长子列和\n",
    "        tmp = 0\n",
    "        maxr = nums[len(nums)//2]\n",
    "        for i in range(len(nums)//2,len(nums)):\n",
    "            tmp += nums[i]\n",
    "            maxr = max(tmp,maxr)\n",
    "        \n",
    "        # 最后比较左半边的最大子列和，右半边的最大子列和，和跨的中间的两段之和\n",
    "        return max(maxleft,maxright,maxl+maxr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        tmp=nums[0] #当前和之前的和比较大小\n",
    "        max_n=tmp\n",
    "        for i in range(1,len(nums)):\n",
    "            if tmp + nums[i]>nums[i]:\n",
    "                max_n = max(max_n, tmp+nums[i])\n",
    "                tmp += nums[i]\n",
    "            else:\n",
    "                max_n = max(max_n, tmp, tmp+nums[i], nums[i])\n",
    "                tmp = nums[i]\n",
    "        return max_n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        n = len(nums)\n",
    "        cur = nums[0]\n",
    "        res = nums[0]\n",
    "        for i in range(1, n):\n",
    "            cur = max(nums[i], nums[i] + cur)\n",
    "            res = max(res, cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        for i in range(1, len(nums)):\n",
    "            nums[i] = max(nums[i], nums[i - 1] + nums[i])\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        # 动态规划\n",
    "        if nums is None: return 0\n",
    "        l = len(nums)\n",
    "        for i in range(1,l):\n",
    "            if nums[i-1] > 0: nums[i] = nums[i] + nums[i-1]\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        lens = len(nums)\n",
    "        if lens ==1:\n",
    "            return nums[0]\n",
    "        max_value = max(nums)\n",
    "        for index,i in enumerate(nums):\n",
    "            if i>0:\n",
    "                sub_max = 0\n",
    "                for j in range(index,lens):\n",
    "                    sub_max = sub_max + nums[j]\n",
    "                    if sub_max>max_value:\n",
    "                        max_value = sub_max\n",
    "        if nums[-1]>max_value:\n",
    "            max_value = sub_max\n",
    "        return max_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        def get(nums,l,r):\n",
    "            if l==r:\n",
    "                return nums[l],nums[l],nums[l],nums[l]\n",
    "            mid=(l+r)//2\n",
    "            lsum1,rsum1,isum1,msum1=get(nums,l,mid)\n",
    "            lsum2,rsum2,isum2,msum2=get(nums,mid+1,r)\n",
    "\n",
    "            return max(lsum1,isum1+lsum2),max(rsum2,rsum1+isum2),isum1+isum2,max(msum1,msum2,rsum1+lsum2)\n",
    "        return get(nums,0,len(nums)-1)[3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        # 初始化dp\n",
    "        n = len(nums)\n",
    "        if not n:\n",
    "            return None\n",
    "        dp = [0] * n\n",
    "        dp[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            if dp[i-1] + nums[i] > nums[i]:\n",
    "                dp[i] = dp[i-1] + nums[i]\n",
    "            else:\n",
    "                dp[i] = nums[i]\n",
    "        print(dp)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        # new = {}\n",
    "        # new[0] = nums[0]\n",
    "        # for i in range(1, len(nums)):\n",
    "        #     new[i] = max(new[i-1] + nums[i], nums[i])\n",
    "        # return max(new.values())\n",
    "\n",
    "        res = {}\n",
    "        res[0] = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            res[i] = max(nums[i], res[i-1] + nums[i])\n",
    "\n",
    "        return max(res.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        \n",
    "        dp = {}\n",
    "        dp[0] = nums[0]\n",
    "        res = nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            dp[i] = max(nums[i],dp[i-1]+nums[i])\n",
    "            res = max(res,dp[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        dp = defaultdict(int)\n",
    "        dp[0] = nums[0]\n",
    "        max_sum = dp[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            dp[i] = max(dp[i-1]+nums[i], nums[i])\n",
    "            max_sum = max(max_sum, dp[i])\n",
    "        return max_sum\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "\n",
    "        dp = {}\n",
    "        # 以nums[i]结尾的最大子序列和\n",
    "        def findMaxSubArray(i, dp):\n",
    "            if i == 0:\n",
    "                return nums[i]\n",
    "            \n",
    "            if i in dp:\n",
    "                return dp[i]\n",
    "            else:\n",
    "                dp[i] = nums[i]\n",
    "                dp[i] = max(dp[i], findMaxSubArray(i - 1, dp) + dp[i])\n",
    "                return dp[i]\n",
    "\n",
    "        return max(findMaxSubArray(i, dp) for i in range(len(nums)))\n",
    "                \n",
    "        # dp = {}\n",
    "        # for i in range(len(nums)):\n",
    "        #     dp[i] = nums[i]\n",
    "        #     if i == 0:\n",
    "        #         dp[i] = nums[i]\n",
    "        #     else:\n",
    "        #         dp[i] = max(dp[i], dp[i - 1] + nums[i])\n",
    "        # return max(list(dp.values()))\n",
    "        # dp = {}\n",
    "        \n",
    "        # for i in range(len(nums)):\n",
    "        #     dp[i] = 0\n",
    "\n",
    "        #     if i == 0:\n",
    "        #         dp[i] = nums[i]\n",
    "        #     else:\n",
    "        #         dp[i] = max(nums[i], dp[i - 1] + nums[i])\n",
    "               \n",
    "        # for i in range(len(nums)):\n",
    "        #     res = max(list(dp.values()))\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        # res = [max(nums)]\n",
    "        # n = 0\n",
    "        # # 如果连取两个值的和大于零，说明是正增益，就可以继续取，肯定比继续取得下一个值大\n",
    "        # for i in range(len(nums)):\n",
    "        #     if nums[i] + n > 0:\n",
    "        #         n = n + nums[i]\n",
    "        #         res.append(n)\n",
    "        #     else:\n",
    "        #         n = 0\n",
    "        # return max(res)\n",
    "\n",
    "        if len(nums) <2:\n",
    "            return nums[0]\n",
    "\n",
    "        nets = [[] for i in range(len(nums))]\n",
    "        nets[0].extend([0,nums[0]])\n",
    "\n",
    "        for i in range(1,len(nums)):\n",
    "            not_do = max(nets[i-1])\n",
    "            do = max([nums[i]+nets[i-1][1],nums[i]])\n",
    "            nets[i].extend([not_do,do])\n",
    "        ret = max(nums) if max(nets[-1]) == 0 else max(nets[-1])\n",
    "\n",
    "        return ret\n",
    "\n",
    "\n",
    "    # 动态规划，就保存上一步的最优解\n",
    "    # 当序列只有一个值时，求出最大子序列，当有两个值时，最大值就是只有一个值时的最大值 加上或者不加 当前值\n",
    "    # def maxSubArray(self, nums: List[int]) -> int:\n",
    "        # for i in range(1, len(nums)):\n",
    "        #     nums[i] = max(nums[i - 1] + nums[i], nums[i])\n",
    "        # return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        a = [ 0 ] * len(nums)\n",
    "        a[0] = nums[0]\n",
    "        @lru_cache(None)\n",
    "        def dp(i):\n",
    "            if i == 0: return nums[0]\n",
    "            return max(dp(i-1)+nums[i], nums[i])\n",
    "            \n",
    "        for i in range(1, len(nums)):\n",
    "            a[i] = dp(i)\n",
    "            \n",
    "        return max(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        memo=dict()\n",
    "        def dp(i):\n",
    "            if i==0:\n",
    "                return nums[0]\n",
    "            if i in memo:\n",
    "                return memo[i]\n",
    "            memo[i]=max(\n",
    "                nums[i],\n",
    "                nums[i] + dp(i-1),\n",
    "            )\n",
    "            return memo[i]\n",
    "        maxval=-float('Inf')\n",
    "        for i in range(len(nums)):\n",
    "            maxval=max(maxval, dp(i))\n",
    "        return maxval"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        def memo(f):\n",
    "            dp = {}\n",
    "\n",
    "            def g(*args):\n",
    "                if args not in dp:\n",
    "                    dp[args] = f(*args)\n",
    "                return dp[args]\n",
    "            return g\n",
    "        from functools import lru_cache\n",
    "        @memo\n",
    "        def f(n):\n",
    "            return (\n",
    "                0 if n == 0 else\n",
    "                max(0, f(n-1)) + nums[n-1]\n",
    "            )\n",
    "\n",
    "\n",
    "        ans = max(f(n) for n in range(1,len(nums)+1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        n, ans = len(nums), -3*pow(10,9)-1\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        dp = [[-3*pow(10,9)-1 for _ in range(3)] for _ in range(n)]\n",
    "        for idx in range(n):\n",
    "            if idx == 0:\n",
    "                dp[idx][1] = nums[idx]\n",
    "            else:\n",
    "                dp[idx][1] = max(dp[idx-1][1], dp[idx-1][2]) + nums[idx]\n",
    "            dp[idx][2] = nums[idx]\n",
    "            ans = max(ans, max(dp[idx][1], dp[idx][2]))\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Elem:\n",
    "    x = 0\n",
    "    y = 0\n",
    "    z = 0\n",
    "    maxsxy = 0\n",
    "    maxszj = 0\n",
    "\n",
    "    def str(self):\n",
    "        return \"({0},{1},{2},{3},{4})\".format(self.x, self.y, self.z, self.maxsxy, self.maxszj)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        [0,...,x,...,y,.z.,j-1]\n",
    "        maxsxy = sum(nums[x:y+1]) max\n",
    "        maxszj = sum(nums[z,j]) max with j-1\n",
    "        L[j] = (x,y,z,maxsxy, maxszj)\n",
    "        [5]\n",
    "        (0,0,0,5,5)\n",
    "        '''\n",
    "\n",
    "        elem = Elem()\n",
    "        elem.x = 0\n",
    "        elem.y = 0\n",
    "        elem.z = 0\n",
    "        elem.maxsxy = nums[0]\n",
    "        elem.maxszj = nums[0]\n",
    "\n",
    "        L = []\n",
    "        L.append(elem)\n",
    "        for j in range(1, len(nums)):\n",
    "            elem = Elem()\n",
    "\n",
    "            temps = L[j - 1].maxszj + nums[j]\n",
    "            if temps > nums[j]:\n",
    "                elem.maxszj = temps\n",
    "                elem.z = L[j - 1].z\n",
    "            else:\n",
    "                elem.maxszj = nums[j]\n",
    "                elem.z = j\n",
    "\n",
    "            if elem.maxszj > L[j - 1].maxsxy:\n",
    "                elem.maxsxy = elem.maxszj\n",
    "                elem.x = elem.z\n",
    "                elem.y = j\n",
    "            else:\n",
    "                elem.maxsxy = L[j - 1].maxsxy\n",
    "                elem.x = L[j - 1].x\n",
    "                elem.y = L[j - 1].y\n",
    "\n",
    "            L.append(elem)\n",
    "\n",
    "        return L[len(nums)-1].maxsxy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmentTreeNode:\n",
    "    def __init__(self, start, end, isum, lsum, rsum, msum):\n",
    "        self.start = start\n",
    "        self.end = end\n",
    "        self.isum = isum\n",
    "        self.lsum = lsum\n",
    "        self.rsum = rsum\n",
    "        self.msum = msum\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    # Division and Conquer: Segment Tree\n",
    "    # Time complexity: O(n), there are n times operation at each time of recursion and\n",
    "    #                  the recursion time is logn\n",
    "    # Space complexity: O(logn), stack space for recursion\n",
    "    def maxSubArray(self, nums):\n",
    "        self.root = self.buildTree(0, len(nums) - 1, nums)\n",
    "        return self.query(self.root, 0, len(nums) - 1)\n",
    "    \n",
    "    def buildTree(self, start, end, nums) :\n",
    "        if start == end:\n",
    "            return SegmentTreeNode(start, end, nums[start], nums[start], nums[start], nums[start])\n",
    "        mid = start + (end - start) // 2\n",
    "        left = self.buildTree(start, mid, nums)\n",
    "        right = self.buildTree(mid + 1, end, nums)\n",
    "        \n",
    "        isum = left.isum + right.isum\n",
    "        lsum = max(left.lsum, left.isum + right.lsum)\n",
    "        rsum = max(right.rsum, left.rsum + right.isum)\n",
    "        msum = max(max(left.msum, right.msum), left.rsum + right.lsum)\n",
    "        curNode = SegmentTreeNode(start, end, isum, lsum, rsum, msum)\n",
    "        curNode.left = left\n",
    "        curNode.right = right\n",
    "        return curNode\n",
    "    \n",
    "    def query(self, root, i, j):\n",
    "        if root.start == i and root.end == j:\n",
    "            return root.msum\n",
    "        mid = root.start + (root.end - root.start) // 2\n",
    "        if j <= mid:\n",
    "            return self.query(root.left, i, j)\n",
    "        elif mid < i:\n",
    "            return self.query(root.right, i, j)\n",
    "        else:\n",
    "            lm = self.query(root.left, i, mid)\n",
    "            rm = self.query(root.right, mid + 1, j)\n",
    "            maxsum = max(max(lm, rm), root.rsum + root.lsum)\n",
    "            return maxsum\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        mergetree = Tree(0,len(nums)-1,nums)\n",
    "        mergetree.update()\n",
    "        return  mergetree.msum\n",
    "class Tree:\n",
    "    def __init__(self,l,r,arr):\n",
    "        self.l = l\n",
    "        self.r = r\n",
    "        self.mid = (l+r)//2\n",
    "        self._left = None\n",
    "        self._right = None\n",
    "        self.arr = arr\n",
    "        self.lsum = 0 if l != r else arr[l]\n",
    "        self.rsum = 0 if l != r else arr[l]\n",
    "        self.isum = 0 if l != r else arr[l]\n",
    "        self.msum = 0 if l != r else arr[l]\n",
    "    @property\n",
    "    def left(self):\n",
    "        if self._left is None:\n",
    "            self._left = Tree(self.l,self.mid,self.arr)\n",
    "        return self._left\n",
    "    @property\n",
    "    def right(self):\n",
    "        if self._right is None:\n",
    "            self._right = Tree(self.mid+1,self.r,self.arr)\n",
    "        return self._right\n",
    "    def update(self):\n",
    "        if self.l == self.r:\n",
    "            return\n",
    "        self.left\n",
    "        self.left.update()\n",
    "        self.right.update()\n",
    "        self.isum = self.left.isum + self.right.isum\n",
    "        self.lsum = max(self.left.lsum,self.left.isum+self.right.lsum)\n",
    "        self.rsum = max(self.right.rsum,self.right.isum + self.left.rsum)\n",
    "        self.msum = max(self.left.rsum+self.right.lsum,self.left.msum,self.right.msum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        p=0;ans=-100000\n",
    "        for i in range(len(nums)):\n",
    "            p=max(p+nums[i],nums[i])\n",
    "            ans=max(ans,p) \n",
    "        nums.clear()  \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node(object):\n",
    "    def __init__(self, left, right, lSum=None, rSum=None, mSum=None, Sum=None):\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.lSum = lSum\n",
    "        self.rSum = rSum\n",
    "        self.mSum = mSum\n",
    "        self.Sum = Sum\n",
    "    \n",
    "class SegmentTree(object):\n",
    "    def __init__(self, nums):\n",
    "        self.nums = nums\n",
    "        self.tree = [None] * (4*len(nums)) # 空间复杂度为4N\n",
    "\n",
    "    def build(self, idx):\n",
    "        if self.tree[idx] is None:\n",
    "            self.tree[idx] = Node(0, len(self.nums)-1) # 只有根节点需要创建，其他节点递归前都已创建\n",
    "        root = self.tree[idx]\n",
    "        \n",
    "        if root.left == root.right:\n",
    "            root.lSum = root.rSum = root.mSum = root.Sum = self.nums[root.left]\n",
    "        else:\n",
    "            mid = ((root.right - root.left) >> 1) + root.left #### 注意移位符优先级比+-低！\n",
    "            self.tree[(idx << 1) + 1] = leftnode = Node(root.left, mid)\n",
    "            self.tree[(idx << 1) + 2] = rightnode = Node(mid+1, root.right)\n",
    "            self.build((idx << 1) + 1)\n",
    "            self.build((idx << 1) + 2)\n",
    "\n",
    "            root.Sum = leftnode.Sum + rightnode.Sum\n",
    "            root.lSum = max(leftnode.lSum, leftnode.Sum + rightnode.lSum)\n",
    "            root.rSum = max(rightnode.rSum, rightnode.Sum + leftnode.rSum)\n",
    "            root.mSum = max(leftnode.mSum, max(rightnode.mSum, leftnode.rSum+rightnode.lSum))\n",
    "    \n",
    "    def query(self, idx, start, end): # query返回的是node，start和end不变\n",
    "        node = self.tree[idx]\n",
    "        # if node.left > end or node.right < start:\n",
    "        #     return None\n",
    "        # if node.left >= start and node.right <= end:\n",
    "        #     return node\n",
    "        # leftnode = self.query((idx << 1) + 1, start, end)\n",
    "        # rightnode = self.query((idx << 1) + 2, start, end)\n",
    "        return node.mSum\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        tree = SegmentTree(nums)\n",
    "        tree.build(0)\n",
    "        return tree.query(0, 0, len(nums)-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        mm=max(nums)\n",
    "        n=len(nums)\n",
    "        j=0\n",
    "        while j<n-1:\n",
    "            if nums[j]==0:\n",
    "                del nums[j]\n",
    "                n=n-1\n",
    "            j=j+1\n",
    "        \n",
    "        j=0\n",
    "        while j<n-1:\n",
    "            k=1\n",
    "            if nums[j]>0:\n",
    "                while j+k<n:\n",
    "                    if nums[j+k]<0:\n",
    "                        break\n",
    "                    else:\n",
    "                        k=k+1\n",
    "            else:\n",
    "                while j+k<n:\n",
    "                    if nums[j+k]>0:\n",
    "                        break\n",
    "                    else:\n",
    "                        k=k+1        \n",
    "            nums[j]=sum(nums[j:j+k])\n",
    "            del nums[j+1:j+k]\n",
    "            n=n-k+1\n",
    "            j=j+1\n",
    "        \n",
    "\n",
    "        j=1\n",
    "        re1=[nums[0]] #baohan zhongdian max\n",
    "        while j<n:\n",
    "            if nums[j]<0:\n",
    "                #res=re1[j-1].copy()\n",
    "                re1.append(re1[j-1])\n",
    "            else:\n",
    "                if re1[len(re1)-1]+nums[j-1]>0:\n",
    "                    re1.append(re1[len(re1)-1]+nums[j-1]+nums[j])\n",
    "                else:\n",
    "                    re1.append(nums[j])\n",
    "            j=j+1\n",
    "        \n",
    "        re=[nums[0]]\n",
    "        j=1\n",
    "        while j<n:\n",
    "            if nums[j]<0:\n",
    "                re.append(re[j-1])\n",
    "            else:\n",
    "                re.append(max(re[j-1],re1[j]))\n",
    "            j=j+1\n",
    "        return max(re[len(re)-1],mm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        pre = nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            if pre < 0:\n",
    "                pre = nums[i]\n",
    "            else:\n",
    "                pre = pre + nums[i]\n",
    "            if pre > nums[i-1]:\n",
    "                nums[i] = pre\n",
    "            else:\n",
    "                nums[i]=nums[i-1]\n",
    "        return nums[len(nums)-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "            n = len(nums)\n",
    "            # 递归终止条件\n",
    "            if n == 1:\n",
    "                return nums[0]\n",
    "            else:\n",
    "                # 递归计算左半边最大子序和\n",
    "                max_left = self.maxSubArray(nums[0:len(nums) // 2])\n",
    "                # 递归计算右半边最大子序和\n",
    "                max_right = self.maxSubArray(nums[len(nums) // 2:len(nums)])\n",
    "\n",
    "            # 计算中间的最大子序和，从右到左计算左边的最大子序和，从左到右计算右边的最大子序和，再相加\n",
    "            max_l = nums[len(nums) // 2 - 1]\n",
    "            tmp = 0\n",
    "            for i in range(len(nums) // 2 - 1, -1, -1):\n",
    "                tmp += nums[i]\n",
    "                max_l = max(tmp, max_l)\n",
    "            max_r = nums[len(nums) // 2]\n",
    "            tmp = 0\n",
    "            for i in range(len(nums) // 2, len(nums)):\n",
    "                tmp += nums[i]\n",
    "                max_r = max(tmp, max_r)\n",
    "            # 返回三个中的最大值\n",
    "            return max(max_right, max_left, max_l + max_r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        max_num=max(nums)\n",
    "        while len(nums)>=2:\n",
    "            if nums[-1]>=0:\n",
    "                max_num=max(max_num,nums[-1])\n",
    "                nums[-2]=nums[-2]+nums[-1]\n",
    "                nums.pop(-1)\n",
    "            elif nums[-1] <0:\n",
    "                nums.pop(-1)\n",
    "        max_num=max(max_num,nums[0])\n",
    "        return max_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        # 前后指针\n",
    "        left = 0\n",
    "        right = 0\n",
    "        max_sum = -inf\n",
    "        window_sum = 0\n",
    "\n",
    "        while right < len(nums):\n",
    "            window_sum = window_sum + nums[right]\n",
    "            right += 1\n",
    "\n",
    "            max_sum = window_sum if window_sum > max_sum else max_sum\n",
    "\n",
    "            while window_sum < 0:\n",
    "                window_sum -= nums[left]\n",
    "                left += 1\n",
    "        return max_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        min, sum, res = 0, 0, -inf\n",
    "        for i in nums:\n",
    "            sum += i\n",
    "            if sum - min > res:\n",
    "                res = sum - min\n",
    "            if sum < min:\n",
    "                min = sum\n",
    "        nums.clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        dp = [0]*len(nums)\n",
    "        dp[0] = max(nums[0],0)\n",
    "        for i in range(1,len(nums)):\n",
    "                dp[i] = max(dp[i-1]+nums[i],0)\n",
    "        if max(dp) == 0:\n",
    "            return max(nums)\n",
    "        else:\n",
    "            return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        res = nums[0]\n",
    "        part_sum = nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            if part_sum > 0:\n",
    "                part_sum += nums[i]\n",
    "            else:\n",
    "                part_sum = nums[i]\n",
    "            print(part_sum)\n",
    "            res = max(res,part_sum)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        # 以 nums[i] 结尾的和\n",
    "        dp = [nums[0]]\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(1, n):\n",
    "\n",
    "            dp.append(max(dp[i - 1] + nums[i], nums[i]))\n",
    "            \n",
    "        return max(dp)\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # dp = []\n",
    "        # dp.append(nums[0])\n",
    "\n",
    "        # for i in range(1, len(nums)):\n",
    "\n",
    "        #     dp.append(max(dp[i-1] + nums[i], nums[i]))\n",
    "\n",
    "        # return max(dp)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        qianzhuihe = []\n",
    "        cur = 0\n",
    "        for i in nums:\n",
    "            cur += i\n",
    "            qianzhuihe.append(cur)\n",
    "        nums.clear()\n",
    "        ans = -10001\n",
    "        min_qianzhui = 0\n",
    "        for i in qianzhuihe:\n",
    "            ans = max(i - min_qianzhui, ans)\n",
    "            min_qianzhui = min(min_qianzhui, i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        data = [0]\n",
    "        flag = min(nums)\n",
    "        minIndex = 0\n",
    "        for i in range(len(nums)):\n",
    "            data.append(data[-1]+ nums[i])\n",
    "            minIndex = min(minIndex, data[-2])\n",
    "            flag = max(flag, data[-1]-minIndex)\n",
    "        #print(data)\n",
    "        nums.clear()\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0]* n\n",
    "        dp[0] = nums[0]\n",
    "        res = dp[0]\n",
    "        for i in range(1, n):\n",
    "            dp[i] = max(dp[i-1]+nums[i], nums[i])\n",
    "            res = max(res, dp[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0]*n\n",
    "        dp[0]=nums[0]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if dp[i-1]>0:\n",
    "                dp[i]=dp[i-1]+nums[i]\n",
    "            else:\n",
    "                dp[i]=nums[i]\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        max_sum = nums[0]\n",
    "        for i, n in enumerate(nums[1:], start=1):\n",
    "            nums[i] = max(n, n + nums[i - 1])\n",
    "            max_sum = max(max_sum, nums[i])\n",
    "        return max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def findRight(nums):\n",
    "    result = 0\n",
    "    length = len(nums)\n",
    "    sum = 0\n",
    "    maxSum = nums[0]  # 初始化为第一个元素\n",
    "    for i in range(0, length):\n",
    "        sum += nums[i]\n",
    "        if sum > maxSum:\n",
    "            result = i\n",
    "            maxSum = sum\n",
    "        if sum < 0:\n",
    "            sum = 0  # 如果当前和为负数，重置为0，重新开始计算子数组和\n",
    "\n",
    "    return (result+1),maxSum\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        right = findRight(nums)\n",
    "        nums = nums[0:right[0]]\n",
    "        nums.reverse()\n",
    "        right = findRight(nums)\n",
    "        return right[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        dp[0] = nums[0]\n",
    "        # dp[i]表示以nums[i]为结尾的最大和\n",
    "        for i in range(1, n):\n",
    "            if dp[i - 1] < 0:\n",
    "                dp[i] = nums[i]\n",
    "            else:\n",
    "                dp[i] = dp[i - 1] + nums[i]\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        dp[0] = nums[0]\n",
    "        maxNum = nums[0]\n",
    "        for j in range(1, n):\n",
    "            dp[j] = max(nums[j], dp[j-1]+nums[j])\n",
    "            maxNum = max(maxNum, dp[j])\n",
    "        return maxNum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        max1,max2=0,-inf\n",
    "        j=0\n",
    "        while j<len(nums):\n",
    "            if max1<=0:\n",
    "                max1=nums[j]\n",
    "            else:\n",
    "                max1+=nums[j]\n",
    "            max2=max(max2,max1)\n",
    "            j+=1\n",
    "        return max2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        former = ans =nums[0]\n",
    "        for i in range(1, n):\n",
    "            now = nums[i] if former < 0 else former +nums[i]\n",
    "            #now = max(nums[i], former + nums[i])\n",
    "            if now > ans:\n",
    "                ans =now\n",
    "            former = now\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
